package com.ohc.算法.排序;

import com.ohc.工具类.tools.Integers;

import java.util.Arrays;

/**
 * @Author 欧皓辰
 * @Date 2021/12/20 23:15
 * @Version 1.0
 */
public class 冒泡排序 {
    /**
     * 从头开始比较相邻的元素，如果第一个元素比第二个大，就交换它们的位置。
     * 一个一个的扫描，扫描一轮以后最大的元素就已经确定在最后面了，
     * 所以在第二轮扫描会从头开始继续扫描，忽略最后一个。
     */
    public static void main(String[] args) {
        bubbleSort02();
    }


    /**
     * 优化一，
     * 这种优化的方案，多了一些优化的指令，效率往往会低一些，
     * 一开始就有序的情况是比较少见的。
     */
    public static void bubbleSort01() {
        int[] array = {10, 9, 5, 12, 20, 30, 11};
        for (int end = array.length - 1; end > 0; end--) {
            boolean sorted = true; // 假定是有序的，有可能在经过某一轮的比较排序的就已经有序了
            for (int begin = 1; begin <= end; begin++) {  // 如果没有外层循环就是一轮比较。因为每次的末尾要变化，所以需要有个外层循环来控制
                if (array[begin] < array[begin - 1]) {  // 说明左边的比较大。
                    int tmp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = tmp;
                    sorted = false;  // 到这里说明就不是有序的
                }
            }
            if (sorted) break; // 到这里说明就已经有序了，直接跳出最外循环。
        }
        for (int i = 0; i < array.length; i++) {
            System.out.println("array[i] = " + array[i]);
        }
    }

    /**
     * 优化2  如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数。
     * 2  1    5  6 7
     * 最坏、平均时间复杂度 为 o(n^2)
     * 最好时间复杂度 ： o(n)
     * 空间复杂度  O(1)
     */
    public static void bubbleSort02() {
        Integer[] array = Integers.random(10, 0, 150);
        for (int end = array.length - 1; end > 0; end--) {
//            sortedIndex 在数组完全有序的时候有用。。
            int sortedIndex = 1;
            for (int begin = 1; begin <= end; begin++) {  // 如果没有外层循环就是一轮比较。因为每次的末尾要变化，所以需要有个外层循环来控制
                if (array[begin] < array[begin - 1]) {  // 说明左边的比较大。
                    int tmp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = tmp;
                    sortedIndex = begin;  // 记录最后一次交换的位置。
                }
            }
            end = sortedIndex;
        }
        for (int i = 0; i < array.length; i++) {
            System.out.println("array[i] = " + array[i]);
        }
    }
}
